package com.example.offer.no0004.impl;

import com.example.offer.no0004.Solution;

/**
 * @author yumuhui <yumuhui@kuaishou.com>
 * 时间复杂度：O(nm)。
 * 二维数组中的每个元素都被遍历，因此时间复杂度为二维数组的大小
 * 空间复杂度：O(1)。
 * Created on 2021-05-13
 */
public class ForSolutionImpl implements Solution {

    @Override
    public boolean findNumberIn2DArray(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        for (int i=0; i<matrix.length; i++) {
            if (matrix[i][0] > target) {
                return false;
            }
            for (int j=0; j<matrix[0].length; j++) {
                if(matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}
